package com.c2b.algorithm.leetcode.base;

/**
 * <a href='https://leetcode.cn/problems/remove-duplicate-letters/'>去除重复字母(Remove Duplicate Letters)</a>
 * <p>给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：s = "bcabc"
 *      输出："abc"
 *
 * 示例 2：
 *      输入：s = "cbacdcbc"
 *      输出："acdb"
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>1 <= s.length <= 10^4</li>
 *     <li>s 由小写英文字母组成</li>
 * </ul>
 * </p>
 * <b>本题同{@link LC1081SmallestSubsequenceOfDistinctCharacters_M}</b>
 *
 * @author c2b
 * @since 2024/3/21 14:08
 */
public class LC0316RemoveDuplicateLetters_M {
    static class Solution {
        public String removeDuplicateLetters(String s) {
            // 统计每个字符出现的次数
            int[] cnt = new int[26];
            // visited 用于当前字符是否出现过
            boolean[] visited = new boolean[26];
            char[] chars = s.toCharArray();
            for (char ch : chars) {
                ++cnt[ch - 'a'];
            }
            StringBuilder sb = new StringBuilder();
            for (char ch : chars) {
                if (!visited[ch - 'a']) {
                    // 当前出现的字符比前面出现的字符的字典序要小。并且前面出现的字符后续还会出现，移除前面的字符
                    // 例如：bab，此时a会将b弹出，因为a后面还有b
                    while (sb.length() > 0 && ch < sb.charAt(sb.length() - 1) && cnt[sb.charAt((sb.length() - 1)) - 'a'] > 0) {
                        visited[sb.charAt(sb.length() - 1) - 'a'] = false;
                        sb.deleteCharAt(sb.length() - 1);
                    }
                    sb.append(ch);
                    visited[ch - 'a'] = true;
                }
                --cnt[ch - 'a'];
            }
            return sb.toString();
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.removeDuplicateLetters("bcabc"));
        System.out.println(solution.removeDuplicateLetters("cbacdcbc"));
    }
}
